LongestPalindromicSubsequence.java

packagesection19_DynamicProgramming;

/*
 * Given a string s, find the longest palindromic subsequence's length in s. 
 */

publicclassLongestPalindromicSubsequence {

publicstaticvoidmain(String[] args) {
// String str = "acdcga"; // 5
// String str = "cbbd"; // 2
// String str = "bbbab"; // 4
Stringstr = "askdfdaoshdwqeyrqwpeawqtewuroiuaSBAadisidhqpweus"; // 19

intsi = 0, ei = str.length() - 1;

// System.out.println(longPalindromicSubseqRec(str, si, ei));

int[][] storage = newint[str.length()][str.length()];

System.out.println(LPSTopDownDP(str, si, ei, storage));
System.out.println(LPSBottomUpDP(str));
 }

publicstaticintlongPalindromicSubseqRec(Stringstr, intsi, intei) {
if (ei < si)
return0;

if (si == ei) {
return1;
 }
intstart = str.charAt(si);
intend = str.charAt(ei);

intpalindromicLen = 0;

if (start == end) {
palindromicLen = 2 + longPalindromicSubseqRec(str, si + 1, ei - 1);
 } else {
intremoveFirst = longPalindromicSubseqRec(str, si + 1, ei);
intremoveLast = longPalindromicSubseqRec(str, si, ei - 1);

intans = Math.max(removeFirst, removeLast);

palindromicLen += ans;
 }

returnpalindromicLen;
 }

publicstaticintLPSTopDownDP(Stringstr, intsi, intei, int[][] storage) {
if (ei < si)
return0;
if (si == ei) {
return1;
 }

if (storage[si][ei] != 0) { // reuse
returnstorage[si][ei];
 }
intpalindromicLen = 0;

if (str.charAt(si) == str.charAt(ei)) {
palindromicLen = 2 + LPSTopDownDP(str, si + 1, ei - 1, storage);
 } else {
intremoveFirst = LPSTopDownDP(str, si + 1, ei, storage);
intremoveLast = LPSTopDownDP(str, si, ei - 1, storage);

palindromicLen = Math.max(removeFirst, removeLast);
 }

storage[si][ei] = palindromicLen;

returnpalindromicLen;
 }

publicstaticintLPSBottomUpDP(Stringstr) {
intn = str.length();

int[][] storage = newint[n][n];

// for (int i = 0; i < storage.length; i++) {
// Arrays.fill(storage[i], 1);
// }
// for (int row = n - 2; row >= 0; row--) {
// for (int col = row + 1; col < n; col++) {

for (intslide = 0; slide <= n - 1; slide++) {

for (intsi = 0; si <= n - slide - 1; si++) {

intei = slide + si;

// logic from top down
if (si == ei) {
storage[si][ei] = 1;
 } else {
intpalindromicLen = 0;

if (str.charAt(si) == str.charAt(ei)) {
palindromicLen = 2 + storage[si + 1][ei - 1];
 } else {
intremoveFirst = storage[si + 1][ei];
intremoveLast = storage[si][ei - 1];
palindromicLen = Math.max(removeFirst, removeLast);
 }

storage[si][ei] = palindromicLen;
 }
 }
 }
returnstorage[0][n - 1];
 }
}